package SwordOffer2;

public class day7_2 {
    /*
     * 1.设置fast，low两个指针，令fast移动是low的2倍
     * 2.指针从head移动，若fast指向null时说明没有环，返回null；若fast与low相遇说明有环
     *   此时low假设走了(a+b)，fast走了(a+b+n(b+c)),a为起点到环的长度，并且fast走的距离时low的2倍，
     *   可以得到 a+b+n(b+c)-(a+b)=2(a+b) ——》 a=c+(n-1)(b+c),
     * 3.设置指针res，使res移动速度等于low，res从head移动，low从f，l相遇位置移动，当相遇时，res移动a，low移动c+(n-1)(b+c）
     *   返回值res
     * */
    public ListNode1 detectCycle(ListNode1 head) {
        ListNode1 fast = head;
        ListNode1 low = head;
        ListNode1 res = head;
        if (fast == null || fast.next == null) {
            return null;
        }
        //第一次相遇
        while (fast != null) {
            //判断无环时，fast是不是最后一个节点，如果是，fast移动一个位置，否则移动两个节点
            if (fast.next == null) {
                fast = fast.next;
            } else {
                fast = fast.next.next;
            }
            low = low.next;
            if (fast == low) {
                break;
            }
        }
        if (fast == null) {
            return fast;
        }
        //第二次相遇
        while (low != res) {
            low = low.next;
            res = res.next;
        }
        return res;
    }
}
